COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	1. Assuming that an environment is a sequence of blocks, and each block
C00014 ENDMK
C⊗;
1. Assuming that an environment is a sequence of blocks, and each block
is a structure with two components, selectable by NAMES and VALUES, we have:

(DE LOOKUP (N ST)
  (COND ((NULL ST) error)
	(T (LOOKUP1 N (NAMES (FIRST ST))(VALUES (FIRST ST)) ST)))) 


(DE LOOKUP1 (N NAMES VALUES ST)
  (COND ((MT-Y NAMES)(LOOKUP N (REST ST)))
	((EQ N (GET-N NAMES)) (GET-V VALUES))
	(T (LOOKUP1 N (TAIL NAMES) (TAIL VALUES) ST))))

where MT-Y, GET-N, TAIL, and GET-V are appropriate recognizers and selectors.
For example, if the names- and values-components are both sequences, then
NULL, FIRST,  REST, and FIRST are implementations of these functions.
--------------------------------------------

2.
in EVAL:

((IS-TEST X) ((LAMBDA (PV)(IF PV
			      ((FUN X) PV)
			      (EVAL (ALT-TEST X) ST)))
	       (EVAL (PRED X) ST)))
--------------------------------------------

3.a
in APPLY:

    ((IS-FUNARG FN) (EVALLIST (REST FN)
			      (MK-ENV (FORM FN)
				      EARGS
				      ENV)))

(DE EVALLIST (L ST)
  (COND ((NULL L) ())
	((NULL (REST L)) (EVAL (FIRST L) ST))
	(T (PROG2 (EVAL (FIRST L) ST)
		  (EVALLIST (REST L) ST)))))

and

(DE PROG2(X Y) Y)

3b: 

in EVAL:

   ((IS-COND X) (EVCOND X ST))

(DE EVCOND (L ST)
  (COND ((NULL L) NIL)
	((EVAL (PRED (FIRST L)) ST) (EVALLIST (REST L) ST))
	(T (EVCOND (REST L) ST)))))
--------------------------------------------

4. 

in EVAL:

  ((IS-DE X) (EVAL (LIST 'SETQ (LHS X) (EVAL (RHS X) ST)) ST))
--------------------------------------------

5. Given the following functions:

(DE PAIR (X Y)
	(LAMBDA (SEL) (IF (EQ SEL 0)
			   X
			   Y)))

(DE HEAD (X) (X 0))           and          (DE TAIL (X) (X 1))

evaluate:     (HEAD (PAIR 'A 'B))  and   (TAIL (PAIR 1 2))
--------------------------------------------

6.  

(DE L-N-R (TR)
  (COND ((EMPTY TR) (MK-EMPTY-TR))
	(T (L-N-R (LEFT TR))
	   (VISIT (NODE TR))
	   (L-N-R (RIGHT TR))))


evaluation strongly depends on left-to-right evaluation in EVAL-APPLY


Suggest a sequence implementation  of these trees  and supply appropriate  selectors,
recognizers, and constructors.
--------------------------------------------

7. Prove that (APPEND X (APPEND Y Z)) ≡ (APPEND (APPEND X Y) Z)
induction on X:

X: ()
(APPEND () (APPEND Y Z)) ≡ (APPEND Y Z) 
(APPEND (APPEND () Y) Z) ≡ (APPEND Y Z)

assume  true for lists, L, of length n; consider
X: (CONCAT α L)

(APPEND (CONCAT α L) (APPEND Y Z)) ≡  (CONCAT α (APPEND L (APPEND Y Z)))

(APPEND (APPEND (CONCAT α L) Y) Z) ≡ (APPEND (CONCAT α (APPEND L Y)) Z)

by induction,  (CONCAT α (APPEND L (APPEND Y Z))) ≡ 
(CONCAT α (APPEND (APPEND L Y) Z)) and by definition of APPEND
is (APPEND (CONCAT α (APPEND L Y)) Z)
--------------------------------------------

8. Assuming a representation  of sets as sequences, write algorithms  for set  union,
intersection, and power set (the set of all subsets of a set).  Write a predicate  to
test for set membership.
--------------------------------------------

9. Consider, the Towers  of Hanoi puzzle:  given three vertical rods  and a stack  of
discs on one rod, arranged by size such  that the largest is on the bottom; move  the
discs to the adjacent rod, subject to the constraints that only one disc may be moved
at a time, and no disc may be placed on top of a smaller disc.

Write a recursive algorithm to describe  the solution, and give a justification  that
your solution is correct.

(DE HANOI (N SOURCE DESTINATION SPARE)
  (COND ((EQ N 1) (MOVE SOURCE DESTINATION))
	(T (HANOI (SUB1 N) SPARE DESTINATION)
	   (MOVE SOURCE DESTINATION)
	   (HANOI (SUB1 N) SPARE DESTINATION SOURCE)))